home *** CD-ROM | disk | FTP | other *** search
/ The PC-SIG Library 10 / The PC-Sig Library - Shareware for the IBM PC and Compatibles (PC-SIG)(Tenth Edition Disks 1-2804)(1991).iso / PC_SIGCD / 22 / 4 / DISK2247.ZIP / CBASE101.ZIP / BTREE101.ZIP / NDOPS.C < prev    next >
Text File  |  1990-06-20  |  30KB  |  1,175 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)ndops.c    1.4 - 90/06/20" */
  5.  
  6. #include <blkio.h>
  7. #include <bool.h>
  8. #include <errno.h>
  9. /*#include <stdlib.h>*/
  10. /*#include <string.h>*/
  11.  
  12. /* local headers */
  13. #include "btree_.h"
  14.  
  15. /*man---------------------------------------------------------------------------
  16. NAME
  17.      bt_ndalloc - allocate memory for node
  18.  
  19. SYNOPSIS
  20.      #include "btree_.h"
  21.  
  22.      btnode_t *bt_ndalloc(btp)
  23.      btree_t *btp;
  24.  
  25. DESCRIPTION
  26.      The bt_ndalloc function allocates an initialized in-core node for
  27.      btree btp.  The address of the node created is returned.
  28.  
  29.      bt_ndalloc will fail if one or more of the following is true:
  30.  
  31.      [EINVAL]       btp is not a valid btree pointer.
  32.      [ENOMEM]       Not enough memory is available for allocation by
  33.                     the calling process.
  34.      [BTENOPEN]     btp is not open.
  35.  
  36. SEE ALSO
  37.      bt_ndfree, bt_ndinit.
  38.  
  39. DIAGNOSTICS
  40.      On failure, a NULL pointer is returned, and errno set to indicate
  41.      the error.
  42.  
  43. ------------------------------------------------------------------------------*/
  44. btnode_t *bt_ndalloc(btp)
  45. btree_t *btp;
  46. {
  47.     btnode_t *btnp = NULL;
  48. #ifdef DEBUG
  49.     /* validate arguments */
  50.     if (!bt_valid(btp)) {
  51.         BTEPRINT;
  52.         errno = EINVAL;
  53.         return NULL;
  54.     }
  55.  
  56.     /* check if not open */
  57.     if (!(btp->flags & BTOPEN)) {
  58.         BTEPRINT;
  59.         errno = BTENOPEN;
  60.         return NULL;
  61.     }
  62. #endif
  63.     /* allocate storage for main node structure */
  64.     /* (calloc is used throughout to automatically set all bits 0) */
  65.     btnp = (btnode_t *)calloc((size_t)1, sizeof(btnode_t));
  66.     if (btnp == NULL) {
  67.         BTEPRINT;
  68.         errno = ENOMEM;
  69.         return NULL;
  70.     }
  71.     btnp->lsib = NIL;
  72.     btnp->rsib = NIL;
  73.     btnp->n = 0;
  74.     /* key array [1..m] (extra slot is for overflow) */
  75.     btnp->keyv = calloc((size_t)btp->bthdr.m, btp->bthdr.keysize);
  76.     if (btnp->keyv == NULL) {
  77.         BTEPRINT;
  78.         free(btnp);
  79.         errno = ENOMEM;
  80.         return NULL;
  81.     }
  82.     /* child node file postion array [0..m] */
  83.     btnp->childv = (bpos_t *)calloc((size_t)(btp->bthdr.m + 1), sizeof(*btnp->childv));
  84.     if (btnp->childv == NULL) {
  85.         BTEPRINT;
  86.         free(btnp->keyv);
  87.         free(btnp);
  88.         errno = ENOMEM;
  89.         return NULL;
  90.     }
  91.  
  92.     errno = 0;
  93.     return btnp;
  94. }
  95.  
  96. /*man---------------------------------------------------------------------------
  97. NAME
  98.      bt_ndcopy - copy btree node
  99.  
  100. SYNOPSIS
  101.      #include "btree_.h"
  102.  
  103.      int bt_ndcopy(btp, tbtnp, sbtnp)
  104.      btree_t *btp;
  105.      btnode_t *tbtnp;
  106.      const btnode_t *sbtnp;
  107.  
  108. DESCRIPTION
  109.      The bt_ndcopy function makes an exact copy of the in-core node
  110.      pointed to by sbtnp to the in-core node pointed to by tbtnp.
  111.  
  112.      bt_ndcopy will fail if one or more of the following is true:
  113.  
  114.      [EINVAL]       btp is not a valid btree pointer.
  115.      [EINVAL]       tbtnp or sbtnp is the NULL pointer.
  116.  
  117. DIAGNOSTICS
  118.      Upon successful completion, a value of 0 is returned.  Otherwise,
  119.      a value of -1 is returned, and errno set to indicate the error.
  120.  
  121. ------------------------------------------------------------------------------*/
  122. int bt_ndcopy(btp, tbtnp, sbtnp)
  123. btree_t *btp;
  124. btnode_t *tbtnp;
  125. const btnode_t *sbtnp;
  126. {
  127. #ifdef DEBUG
  128.     /* validate arguments */
  129.     if (!bt_valid(btp) || tbtnp == NULL || sbtnp == NULL) {
  130.         BTEPRINT;
  131.         errno = EINVAL;
  132.         return -1;
  133.     }
  134. #endif
  135.     /* copy node sbtnp into tbtnp */
  136.     tbtnp->lsib = sbtnp->lsib;
  137.     tbtnp->rsib = sbtnp->rsib;
  138.     tbtnp->n = sbtnp->n;
  139.     memcpy(bt_kykeyp(btp, tbtnp, 1), bt_kykeyp(btp, sbtnp, 1), (size_t)(btp->bthdr.m * btp->bthdr.keysize));
  140.     memcpy(bt_kychildp(tbtnp, 0), bt_kychildp(sbtnp, 0), (size_t)((btp->bthdr.m + 1) * sizeof(*bt_kychildp(tbtnp, 0))));
  141.  
  142.     errno = 0;
  143.     return 0;
  144. }
  145.  
  146. /*man---------------------------------------------------------------------------
  147. NAME
  148.      bt_nddelkey - delete key from btree node
  149.  
  150. SYNOPSIS
  151.      #include "btree_.h"
  152.  
  153.      int bt_nddelkey(btp, btnp, kn)
  154.      btree_t *btp;
  155.      btnode_t *btnp;
  156.      int kn;
  157.  
  158. DESCRIPTION
  159.      The bt_nddelkey function deletes the tuple kn from the in-core
  160.      node pointed to by btnp.
  161.  
  162.      bt_nddelkey will fail if one or more of the following is true:
  163.  
  164.      [EINVAL]       btp is not a valid btree pointer.
  165.      [EINVAL]       btnp is the NULL pointer.
  166.  
  167. SEE ALSO
  168.      bt_ndinskey, bt_ndsearch.
  169.  
  170. DIAGNOSTICS
  171.      Upon successful completion, a value of 0 is returned.  Otherwise,
  172.      a value of -1 is returned, and errno set to indicate the error.
  173.  
  174. ------------------------------------------------------------------------------*/
  175. int bt_nddelkey(btp, btnp, kn)
  176. btree_t *btp;
  177. btnode_t *btnp;
  178. int kn;
  179. {
  180. #ifdef DEBUG
  181.     /* validate arguments */
  182.     if (!bt_valid(btp) || btnp == NULL) {
  183.         BTEPRINT;
  184.         errno = EINVAL;
  185.         return -1;
  186.     }
  187. #endif
  188.     /* delete key kn */
  189.     if (bt_kyshift(btp, btnp, kn + 1, -1) == -1) {
  190.         BTEPRINT;
  191.         return -1;
  192.     }
  193.  
  194.     errno = 0;
  195.     return 0;
  196. }
  197.  
  198. /*man---------------------------------------------------------------------------
  199. NAME
  200.      bt_ndfree - free in-core node
  201.  
  202. SYNOPSIS
  203.      #include "btree_.h"
  204.  
  205.      void bt_ndfree(btnp)
  206.      btnode_t *btnp;
  207.  
  208. DESCRIPTION
  209.      The bt_ndfree function frees the in-core node pointed to by btnp.
  210.  
  211. SEE ALSO
  212.      bt_ndalloc.
  213.  
  214. ------------------------------------------------------------------------------*/
  215. void bt_ndfree(btnp)
  216. btnode_t *btnp;
  217. {
  218.     if (btnp == NULL) {
  219.         return;
  220.     }
  221.     if (btnp->keyv != NULL) free(btnp->keyv);
  222.     btnp->keyv = NULL;
  223.     if (btnp->childv != NULL) free(btnp->childv);
  224.     btnp->childv = NULL;
  225.     free(btnp);
  226.  
  227.     return;
  228. }
  229.  
  230. /*man---------------------------------------------------------------------------
  231. NAME
  232.      bt_ndfuse - btree node fuse
  233.  
  234. SYNOPSIS
  235.      #include "btree_.h"
  236.  
  237.      int bt_ndfuse(btp, lbtnp, rbtnp, pbtnp, pkn)
  238.      btree_t *btp;
  239.      btnode_t *lbtnp;
  240.      btnode_t *rbtnp;
  241.      btnode_t *pbtnp;
  242.      int pkn;
  243.  
  244. DESCRIPTION
  245.      The bt_ndfuse function fuses two nodes.  lbtnp and rbtnp point to
  246.      in-core copies of nodes to be fused, the left and right sibling,
  247.      respectively.  pbtnp points to an in-core copy of the parent
  248.      node.  pkn is the number of the key in pbtnp whose left child is
  249.      lbtnp and right child is rbtnp.
  250.  
  251.      On return, lbtnp contains the fused node and rbtnp is empty.
  252.      Both the left and right nodes are written to the file.  pbtnp is
  253.      modified during the fusion, but is not written to the file; the
  254.      calling program must write pbtnp to the file.
  255.  
  256.      bt_ndfuse will fail if one or more of the following is true:
  257.  
  258.      [EINVAL]       btp is not a valid btree pointer.
  259.      [EINVAL]       btnp, rbtnp, or pbtnp is NULL.
  260.      [EINVAL]       pkn is less than 1 or greater than pbtnp->n.
  261.      [BTENOPEN]     btp is not open.
  262.      [BTEPANIC]     The total number of keys in lbtnp and rbtnp is
  263.                     too large to fuse into one node.
  264.  
  265. SEE ALSO
  266.      bt_ndshift, bt_ndsplit.
  267.  
  268. DIAGNOSTICS
  269.      Upon successful completion, a value of 0 is returned.  Otherwise,
  270.      a value of -1 is returned, and errno set to indicate the error.
  271.  
  272. ------------------------------------------------------------------------------*/
  273. int bt_ndfuse(btp, lbtnp, rbtnp, pbtnp, pkn)
  274. btree_t *btp;
  275. btnode_t *lbtnp;
  276. btnode_t *rbtnp;
  277. btnode_t *pbtnp;
  278. int pkn;
  279. {
  280.     bttpl_t    bttpl;            /* (key, child address) tuple */
  281.     bool    leaf    = FALSE;    /* leaf node flag */
  282.     bpos_t    lnode    = 0;        /* left node block number */
  283.     bpos_t    rnode    = 0;        /* right node block number */
  284.  
  285.     /* initialize automatic aggregates */
  286.     memset(&bttpl, 0, sizeof(bttpl));
  287. #ifdef DEBUG
  288.     /* validate arguments */
  289.     if (!bt_valid(btp)) {
  290.         BTEPRINT;
  291.         errno = EINVAL;
  292.         return NULL;
  293.     }
  294.     if (lbtnp == NULL || rbtnp == NULL || pbtnp == NUL) {
  295.         BTEPRINT;
  296.         errno = EINVAL;
  297.         return -1;
  298.     }
  299.     if (pkn < 1 || pkn > pbtnp->n) {
  300.         BTEPRINT;
  301.         errno = EINVAL;
  302.         return -1;
  303.     }
  304.  
  305.     /* check if too many keys for fusion */
  306.     if (lbtnp->n + rbtnp->n > bt_ndmax(btp) - (leaf ? 0 : 1)) {
  307.         BTEPRINT;
  308.         errno = BTEPANIC;
  309.         return -1;
  310.     }
  311. #endif
  312.     /* check if leaf */
  313.     if (bt_ndleaf(lbtnp)) {
  314.         leaf = TRUE;
  315.     }
  316.  
  317.     /* get block number of sibling nodes */
  318.     lnode = rbtnp->lsib;
  319.     rnode = lbtnp->rsib;
  320.  
  321.     /* if internal node, bring down parent key pkn */
  322.     if (!leaf) {
  323.         bttpl.keyp = calloc((size_t)1, btp->bthdr.keysize);
  324.         if (bttpl.keyp == NULL) {
  325.             BTEPRINT;
  326.             errno = ENOMEM;
  327.             return -1;
  328.         }
  329.         if (bt_kyread(btp, pbtnp, pkn, &bttpl) == -1) {
  330.             BTEPRINT;
  331.             free(bttpl.keyp);
  332.             return -1;
  333.         }
  334.         bttpl.child = *bt_kychildp(rbtnp, 0);
  335.         if (bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttpl) == -1) {
  336.             BTEPRINT;
  337.             free(bttpl.keyp);
  338.             return -1;
  339.         }
  340.         free(bttpl.keyp);
  341.         bttpl.keyp = NULL;
  342.     }
  343.  
  344.     /* move keys from rbtnp to lbtnp */
  345.     if (bt_kymvleft(btp, lbtnp, rbtnp, rbtnp->n) == -1) {
  346.         BTEPRINT;
  347.         return -1;
  348.     }
  349.  
  350.     /* return right node to free list */
  351.     if (bflpush(btp->bp, &rnode) == -1) {
  352.         BTEPRINT;
  353.         return -1;
  354.     }
  355.  
  356.     /* fix sibling links */        /*L=left N=new right */
  357.     lbtnp->rsib = rbtnp->rsib;    /* L -> N */
  358.     if (lbtnp->rsib == NIL) {    /* L <- N */
  359.         if (leaf) btp->bthdr.last = lnode;
  360.     } else {
  361.         if (bputbf(btp->bp, lbtnp->rsib, offsetof(btnode_t, lsib), &lnode, sizeof(lbtnp->lsib)) == -1) {
  362.             BTEPRINT;
  363.             return -1;
  364.         }
  365.     }
  366.  
  367.     /* initialize in-core copy of right sibling */
  368.     bt_ndinit(btp, rbtnp);
  369.  
  370.     /* delete parent key of right sibling */
  371.     if (bt_nddelkey(btp, pbtnp, pkn) == -1) {
  372.         BTEPRINT;
  373.         return -1;
  374.     }
  375.  
  376.     /* write fused node */
  377.     if (bt_ndput(btp, lnode, lbtnp) == -1) {
  378.         BTEPRINT;
  379.         return -1;
  380.     }
  381.  
  382.     errno = 0;
  383.     return 0;
  384. }
  385.  
  386. /*man---------------------------------------------------------------------------
  387. NAME
  388.      bt_ndget - get btree node from file
  389.  
  390. SYNOPSIS
  391.      #include "btree_.h"
  392.  
  393.      int bt_ndget(btp, node, btnp)
  394.      btree_t *btp;
  395.      bpos_t node;
  396.      btnode_t *btnp;
  397.  
  398. DESCRIPTION
  399.      The bt_ndget function reads the contents of a node into the
  400.      in-core node pointed to by btnp to the file.  node is the block
  401.      number of the node in the file.
  402.  
  403.      bt_ndget will fail if one or more of the following is true:
  404.  
  405.      [EINVAL]       btp is not a valid btree pointer.
  406.      [EINVAL]       btnp is NULL.
  407.      [EINVAL]       node is NIL.
  408.      [EINVAL]       btnp is NULL.
  409.      [BTENOPEN]     btp is not open.
  410.  
  411. SEE ALSO
  412.      bt_ndput.
  413.  
  414. DIAGNOSTICS
  415.      Upon successful completion, a value of 0 is returned.  Otherwise,
  416.      a value of -1 is returned, and errno set to indicate the error.
  417.  
  418. ------------------------------------------------------------------------------*/
  419. int bt_ndget(btp, node, btnp)
  420. btree_t *btp;
  421. bpos_t node;
  422. btnode_t *btnp;
  423. {
  424.     void *buf = NULL;
  425. #ifdef DEBUG
  426.     /* validate arguments */
  427.     if (!bt_valid(btp) || node == NIL || btnp == NULL) {
  428.         BTEPRINT;
  429.         errno = EINVAL;
  430.         return -1;
  431.     }
  432.  
  433.     /* check if not open */
  434.     if (!(btp->flags & BTOPEN)) {
  435.         BTEPRINT;
  436.         errno = BTENOPEN;
  437.         return -1;
  438.     }
  439. #endif
  440.     /* read node from file */
  441.     buf = calloc((size_t)1, bt_blksize(btp));
  442.     if (buf == NULL) {
  443.         BTEPRINT;
  444.         errno = ENOMEM;
  445.         return -1;
  446.     }
  447.     if (bgetb(btp->bp, node, buf) == -1) {
  448.         BTEPRINT;
  449.         free(buf);
  450.         return -1;
  451.     }
  452.  
  453.     /* convert file node to in-core format */
  454.     memcpy(btnp, buf, offsetof(btnode_t, keyv));
  455.     memcpy(btnp->keyv,
  456.         ((char *)buf + offsetof(btnode_t, keyv)),
  457.         ((btp->bthdr.m - 1) * btp->bthdr.keysize));
  458.     memcpy(btnp->childv,
  459.         ((char *)buf + offsetof(btnode_t, keyv) +
  460.             ((btp->bthdr.m - 1) * btp->bthdr.keysize)),
  461.         (btp->bthdr.m * sizeof(*btnp->childv)));
  462.  
  463.     /* free buffer */
  464.     free(buf);
  465.  
  466.     errno = 0;
  467.     return 0;
  468. }
  469.  
  470. /*man---------------------------------------------------------------------------
  471. NAME
  472.      bt_ndinit - initialize in-core node
  473.  
  474. SYNOPSIS
  475.      #include "btree_.h"
  476.  
  477.      void bt_ndinit(btp, btnp)
  478.      btree_t *btp;
  479.      btnode_t *btnp;
  480.  
  481. DESCRIPTION
  482.      The bt_ndinit function initializes the in-core node btnp.
  483.  
  484. ------------------------------------------------------------------------------*/
  485. void bt_ndinit(btp, btnp)
  486. btree_t *btp;
  487. btnode_t *btnp;
  488. {
  489. #ifdef DEBUG
  490.     /* validate arguments */
  491.     if (!bt_valid(btp) || btnp == NULL) {
  492.         BTEPRINT;
  493.         errno = EINVAL;
  494.         return;
  495.     }
  496. #endif
  497.     /* initialize btnp */
  498.     btnp->lsib = NIL;
  499.     btnp->rsib = NIL;
  500.     btnp->n = 0;
  501.     memset(btnp->keyv, 0, (size_t)(btp->bthdr.m * btp->bthdr.keysize));
  502.     memset(btnp->childv, 0, (size_t)((btp->bthdr.m + 1) * sizeof(*btnp->childv)));
  503.  
  504.     return;
  505. }
  506.  
  507. /*man---------------------------------------------------------------------------
  508. NAME
  509.      bt_ndinskey - insert key into btree node
  510.  
  511. SYNOPSIS
  512.      #include "btree_.h"
  513.  
  514.      int bt_ndinskey(btp, btnp, kn, bttplp)
  515.      btree_t *btp;
  516.      btnode_t *btnp;
  517.      int kn;
  518.      const bttpl_t *bttplp;
  519.  
  520. DESCRIPTION
  521.      The bt_ndinskey function inserts bttplp into the knth slot in
  522.      the in-core btree node btnp.  The node is not written to the
  523.      file.
  524.  
  525.      bt_ndinskey will fail if one or more of the following is true:
  526.  
  527.      [EINVAL]       btp is not a valid btree pointer.
  528.      [EINVAL]       btnp is the NULL pointer.
  529.      [EINVAL]       kn is less than 1 or greater than the number of
  530.                     keys in btnp plus 1.
  531.  
  532. SEE ALSO
  533.      bt_nddelkey, bt_ndsearch.
  534.  
  535. DIAGNOSTICS
  536.      Upon successful completion, a value of 0 is returned.  Otherwise,
  537.      a value of -1 is returned, and errno set to indicate the error.
  538.  
  539. ------------------------------------------------------------------------------*/
  540. int bt_ndinskey(btp, btnp, kn, bttplp)
  541. btree_t *btp;
  542. btnode_t *btnp;
  543. int kn;
  544. const bttpl_t *bttplp;
  545. {
  546. #ifdef DEBUG
  547.     /* validate arguments */
  548.     if (!bt_valid(btp) || btnp == NULL || bttplp == NULL) {
  549.         BTEPRINT;
  550.         errno = EINVAL;
  551.         return -1;
  552.     }
  553.     if (kn < 1 || kn > btnp->n + 1) {
  554.         BTEPRINT;
  555.         errno = EINVAL;
  556.         return -1;
  557.     }
  558.  
  559.     /* check if room to insert */
  560.     if (btnp->n >= btp->bthdr.m) {
  561.         BTEPRINT;
  562.         errno = BTEPANIC;
  563.         return -1;
  564.     }
  565. #endif
  566.     /* make an empty slot */
  567.     if (bt_kyshift(btp, btnp, kn, 1) == -1) {
  568.         BTEPRINT;
  569.         return -1;
  570.     }
  571.  
  572.     /* put new key into empty slot */
  573.     if (bt_kywrite(btp, btnp, kn, bttplp) == -1) {
  574.         BTEPRINT;
  575.         return -1;
  576.     }
  577.  
  578.     errno = 0;
  579.     return 0;
  580. }
  581.  
  582. /*man---------------------------------------------------------------------------
  583. NAME
  584.      bt_ndleaf - is btree node leaf
  585.  
  586. SYNOPSIS
  587.      #include "btree_.h"
  588.  
  589.      int bt_ndleaf(btnp)
  590.      btnode_t *btnp;
  591.  
  592. DESCRIPTION
  593.      bt_ndleaf returns a true value if btnp is a leaf node or a false
  594.      value if it is not.  If btnp does not point to a valid in-core
  595.      btree node, the results are undefined.  bt_ndleaf is a macro.
  596.  
  597. SEE ALSO
  598.      bt_ndmax, bt_ndmin.
  599.  
  600. ------------------------------------------------------------------------------*/
  601. /* bt_ndleaf is defined in btree_.h. */
  602.  
  603. /*man---------------------------------------------------------------------------
  604. NAME
  605.      bt_ndmax - maximum keys per node
  606.  
  607. SYNOPSIS
  608.      #include "btree_.h"
  609.  
  610.      int bt_ndmax(btp)
  611.      btree_t *btp;
  612.  
  613. DESCRIPTION
  614.      bt_ndmin returns the maximum number of keys allowable in a node
  615.      of btree btp.  If btp does not point to a valid open btree, the
  616.      results are undefined.  bt_ndmax is a macro.
  617.  
  618. SEE ALSO
  619.      bt_ndleaf, bt_ndmin.
  620.  
  621. ------------------------------------------------------------------------------*/
  622. /* bt_ndmax is defined in btree_.h. */
  623.  
  624. /*man---------------------------------------------------------------------------
  625. NAME
  626.      bt_ndmin - minimum keys per node
  627.  
  628. SYNOPSIS
  629.      #include "btree_.h"
  630.  
  631.      int bt_ndmin(btp)
  632.      btree_t *btp;
  633.  
  634. DESCRIPTION
  635.      bt_ndmin returns the minimum number of keys allowable in a node
  636.      of btree btp.  If btp does not point to a valid open btree, the
  637.      results are undefined.  bt_ndmin is a macro.
  638.  
  639. SEE ALSO
  640.      bt_ndleaf, bt_ndmax.
  641.  
  642. ------------------------------------------------------------------------------*/
  643. /* bt_ndmin is defined in btree_.h. */
  644.  
  645. /*man---------------------------------------------------------------------------
  646. NAME
  647.      bt_ndput - put btree node to file
  648.  
  649. SYNOPSIS
  650.      #include "btree_.h"
  651.  
  652.      int bt_ndput(btp, node, btnp)
  653.      btree_t *btp;
  654.      bpos_t node;
  655.      const btnode_t *btnp;
  656.  
  657. DESCRIPTION
  658.      The bt_ndput function writes the contents of the in-core node
  659.      pointed to by btnp to the file.  node is the block number of the
  660.      node in the file.
  661.  
  662.      bt_ndput will fail if one or more of the following is true:
  663.  
  664.      [EINVAL]       btp is not a valid btree pointer.
  665.      [EINVAL]       btnp is NULL.
  666.      [EINVAL]       node is NIL.
  667.      [EINVAL]       btnp is NULL.
  668.      [BTENOPEN]     btp is not open.
  669.  
  670. SEE ALSO
  671.      bt_ndget.
  672.  
  673. DIAGNOSTICS
  674.      Upon successful completion, a value of 0 is returned.  Otherwise,
  675.      a value of -1 is returned, and errno set to indicate the error.
  676.  
  677. ------------------------------------------------------------------------------*/
  678. int bt_ndput(btp, node, btnp)
  679. btree_t *btp;
  680. bpos_t node;
  681. const btnode_t *btnp;
  682. {
  683.     void *buf = NULL;
  684. #ifdef DEBUG
  685.     /* validate arguments */
  686.     if (!bt_valid(btp) || node == NIL || btnp == NULL) {
  687.         BTEPRINT;
  688.         errno = EINVAL;
  689.         return -1;
  690.     }
  691.  
  692.     /* check if not open */
  693.     if (!(btp->flags & BTOPEN)) {
  694.         BTEPRINT;
  695.         errno = BTENOPEN;
  696.         return -1;
  697.     }
  698. #endif
  699.     /* convert in-core node to file format */
  700.     buf = calloc((size_t)1, bt_blksize(btp));
  701.     if (buf == NULL) {
  702.         BTEPRINT;
  703.         errno = ENOMEM;
  704.         return -1;
  705.     }
  706.     memcpy(buf, btnp, offsetof(btnode_t, keyv));
  707.     memcpy(((char *)buf + offsetof(btnode_t, keyv)),
  708.         btnp->keyv,
  709.         ((btp->bthdr.m - 1) * btp->bthdr.keysize));
  710.     memcpy(((char *)buf + offsetof(btnode_t, keyv) +
  711.             ((btp->bthdr.m - 1) * btp->bthdr.keysize)),
  712.         btnp->childv,
  713.         (btp->bthdr.m * sizeof(*btnp->childv)));
  714.  
  715.     /* write node to file */
  716.     if (bputb(btp->bp, node, buf) == -1) {
  717.         BTEPRINT;
  718.         free(buf);
  719.         return -1;
  720.     }
  721.  
  722.     /* free buffer */
  723.     free(buf);
  724.  
  725.     errno = 0;
  726.     return 0;
  727. }
  728.  
  729. /*man---------------------------------------------------------------------------
  730. NAME
  731.      bt_ndsearch - search btree node
  732.  
  733. SYNOPSIS
  734.      #include "btree_.h"
  735.  
  736.      int bt_ndsearch(btp, btnp, buf, knp)
  737.      btree_t *btp;
  738.      const btnode_t *btnp;
  739.      const void *buf;
  740.      int *knp;
  741.  
  742. DESCRIPTION
  743.      Function searches the in-core node btnp for the key pointed to by
  744.      buf.  On return, the location of the smallest key >= that pointed
  745.      to by buf is in the location pointed to by knp.
  746.  
  747.      bt_ndsearch will fail if one or more of the following is true:
  748.  
  749.      [EINVAL]       btp is not a valid btree pointer.
  750.      [EINVAL]       btnp is NULL.
  751.      [EINVAL]       buf is NULL.
  752.      [EINVAL]       knp is NULL.
  753.  
  754. SEE ALSO
  755.      bt_nddelkey, bt_ndinskey.
  756.  
  757. DIAGNOSTICS
  758.      Upon successful completion, a value of 0 is returned if the key
  759.      was found or a value of 1 is it was not found.  Otherwise, a
  760.      value of -1 is returned, and errno set to indicate the error.
  761.  
  762. ------------------------------------------------------------------------------*/
  763. int bt_ndsearch(btp, btnp, buf, knp)
  764. btree_t *btp;
  765. const btnode_t *btnp;
  766. const void *buf;
  767. int *knp;
  768. {
  769.     int    cmp    = 0;        /* result of key comparison */
  770.     int    fld    = 0;        /* field number */
  771.     bool    found    = FALSE;    /* key found flag */
  772.     int    kn    = 0;        /* key number */
  773. #ifdef DEBUG
  774.     /* validate arguments */
  775.     if (!bt_valid(btp) || btnp == NULL || buf == NULL || knp == NULL) {
  776.         BTEPRINT;
  777.         errno = EINVAL;
  778.         return -1;
  779.     }
  780. #endif
  781.     /* initialize */
  782.     *knp = 0;
  783.  
  784.     /* locate key */
  785.     for (kn = 1; kn <= btnp->n; ++kn) {
  786.         for (fld = 0; fld < btp->fldc; ++fld) {
  787.             cmp = (*btp->fldv[fld].cmp)(bt_kykfp(btp, btnp, kn, fld),
  788.                     (char *)buf + btp->fldv[fld].offset,
  789.                     btp->fldv[fld].len);
  790.             if (cmp != 0) {
  791.                 break;
  792.             }
  793.         }
  794.         if (cmp == 0) {
  795.             found = TRUE;
  796.             break;
  797.         }
  798.         if (btp->fldv[fld].flags & BT_FDSC) {
  799.             if (cmp < 0) break;    /* descending order */
  800.         } else {
  801.             if (cmp > 0) break;    /* ascending order */
  802.         }
  803.     }
  804.     *knp = kn;
  805.  
  806.     errno = 0;
  807.     return (found ? 1 : 0);
  808. }
  809.  
  810. /*man---------------------------------------------------------------------------
  811. NAME
  812.      bt_ndshift - node shift
  813.  
  814. SYNOPSIS
  815.      #include "btree_.h"
  816.  
  817.      int bt_ndshift(btp, lbtnp, rbtnp, pbtnp, pkn, pnode)
  818.      btree_t *btp;
  819.      btnode_t *lbtnp;
  820.      btnode_t *rbtnp;
  821.      btnode_t *pbtnp;
  822.      int pkn;
  823.      bpos_t pnode;
  824.  
  825. DESCRIPTION
  826.      The bt_ndshift function shifts keys between two sibling nodes to
  827.      give them both the same number of keys (+/- 1).  lbtnp and rbtnp
  828.      are in-core copies of the two siblings.  pbtnp is an in-core copy
  829.      of the parent node of the two siblings.  pkn is the number of the
  830.      key in pbtnp whose left child is lbtnp and right child is rbtnp.
  831.  
  832.      The left, right, and parent nodes are written to the file.
  833.  
  834.      bt_ndshift will fail if one or more of the following is true:
  835.  
  836.      [EINVAL]       btp is not a valid btree pointer.
  837.      [EINVAL]       lbtnp, rbtnp, or pbtnp is NULL.
  838.      [EINVAL]       pkn is less than 1 or greater than pbtnp->n.
  839.      [BTENOPEN]     btp is not open.
  840.      [BTEPANIC]     Not enough keys in lbtnp and rbtnp to achieve
  841.                     the minimum number in both nodes.
  842.  
  843. SEE ALSO
  844.      bt_ndfuse, bt_ndsplit.
  845.  
  846. DIAGNOSTICS
  847.      Upon successful completion, a value of 0 is returned.  Otherwise,
  848.      a value of -1 is returned, and errno set to indicate the error.
  849.  
  850. ------------------------------------------------------------------------------*/
  851. int bt_ndshift(btp, lbtnp, rbtnp, pbtnp, pkn, pnode)
  852. btree_t *btp;
  853. btnode_t *lbtnp;
  854. btnode_t *rbtnp;
  855. btnode_t *pbtnp;
  856. int pkn;
  857. bpos_t pnode;
  858. {
  859.     bttpl_t    bttpl;            /* (key, child address) tuple */
  860.     bool    leaf    = FALSE;    /* leaf node flag */
  861.     bool    right    = FALSE;    /* shift direction flag */
  862.     int    ns    = 0;        /* number keys to shift */
  863.  
  864.     /* initialize automatic aggregates */
  865.     memset(&bttpl, 0, sizeof(bttpl));
  866. #ifdef DEBUG
  867.     /* validate arguments */
  868.     if (!bt_valid(btp)) {
  869.         BTEPRINT;
  870.         errno = EINVAL;
  871.         return NULL;
  872.     }
  873.     if (lbtnp == NULL || rbtnp == NULL || pbtnp == NULL) {
  874.         BTEPRINT;
  875.         errno = EINVAL;
  876.         return -1;
  877.     }
  878.     if (pkn < 1 || pkn > pbtnp->n) {
  879.         BTEPRINT;
  880.         errno = EINVAL;
  881.         return -1;
  882.     }
  883.  
  884.     /* check if not open */
  885.     if (!(btp->flags & BTOPEN)) {
  886.         BTEPRINT;
  887.         errno = BTENOPEN;
  888.         return NULL;
  889.     }
  890.  
  891.     /* check if enough keys to shift */
  892. if (lbtnp->n + rbtnp->n < 2 * bt_ndmin(btp)) {
  893.         errno = BTEPANIC;
  894.         return -1;
  895.     }
  896.  
  897.     /* check if too many keys to shift */
  898.     if (lbtnp->n + rbtnp->n > 2 * bt_ndmax(btp)) {
  899.         errno = BTEPANIC;
  900.         return -1;
  901.     }
  902. #endif
  903. /*printf("IN NDSHIFT: pkn = %d, pnode = %lu.\n", pkn, pnode);*/
  904.     /* set leaf and direction flags */
  905.     if (bt_ndleaf(lbtnp)) {
  906.         leaf = TRUE;
  907.     }
  908.     if (lbtnp->n > rbtnp->n) {
  909.         right = TRUE;
  910.     } else {
  911.         right = FALSE;
  912.     }
  913.  
  914.     /* if internal node, bring down parent key pkn */
  915.     if (!leaf) {
  916.         bttpl.keyp = calloc((size_t)1, btp->bthdr.keysize);
  917.         if (bttpl.keyp == NULL) {
  918.             BTEPRINT;
  919.             errno = ENOMEM;
  920.             return -1;
  921.         }
  922.         if (bt_kyread(btp, pbtnp, pkn, &bttpl) == -1) {
  923.             BTEPRINT;
  924.             free(bttpl.keyp);
  925.             return -1;
  926.         }
  927.         bttpl.child = *bt_kychildp(rbtnp, 0);
  928.         if (right) {
  929.             if (bt_ndinskey(btp, rbtnp, 1, &bttpl) == -1) {
  930.                 BTEPRINT;
  931.                 free(bttpl.keyp);
  932.                 return -1;
  933.             }
  934.             *bt_kychildp(rbtnp, 0) = *bt_kychildp(lbtnp, lbtnp->n);
  935.         } else {
  936.             if (bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttpl) == -1) {
  937.                 BTEPRINT;
  938.                 free(bttpl.keyp);
  939.                 return -1;
  940.             }
  941.             *bt_kychildp(lbtnp, lbtnp->n) = *bt_kychildp(rbtnp, 0);
  942.         }
  943.         free(bttpl.keyp);
  944.         bttpl.keyp = NULL;
  945.     }
  946.  
  947.     /* calculate number of keys to shift (+ -> shift to right) */
  948.     ns = (lbtnp->n - rbtnp->n) / 2;
  949.     if (ns < 0) ns = -ns;
  950.  
  951. /*printf("NODES BEFORE SHIFT:\n");
  952. puts("Left:");
  953. bt_dgnode(btp, lbtnp, stdout);
  954. puts("Right:");
  955. bt_dgnode(btp, rbtnp, stdout);*/
  956.     /* shift keys */
  957.     if (right) {
  958.         if (bt_kymvright(btp, lbtnp, rbtnp, ns) == -1) {
  959.             BTEPRINT;
  960.             return -1;
  961.         }
  962.     } else {
  963.         if (bt_kymvleft(btp, lbtnp, rbtnp, ns) == -1) {
  964.             BTEPRINT;
  965.             return -1;
  966.         }
  967.     }
  968. /*printf("NODES AFTER SHIFT BUT BEFORE EXTRACT PARENT KEY:\n");
  969. puts("Left:");
  970. bt_dgnode(btp, lbtnp, stdout);
  971. puts("Right:");
  972. bt_dgnode(btp, rbtnp, stdout);*/
  973.  
  974.     /* bring up new parent key (child of pkn remains right node) */
  975.     if (!leaf) {
  976.         if (lbtnp->n > rbtnp->n) {
  977.             memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, lbtnp, lbtnp->n), btp->bthdr.keysize);
  978.             if (bt_nddelkey(btp, lbtnp, lbtnp->n) == -1) {
  979.                 BTEPRINT;
  980.                 return -1;
  981.             }
  982.         } else {
  983.             memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, rbtnp, 1), btp->bthdr.keysize);
  984.             *bt_kychildp(rbtnp, 0) = *bt_kychildp(rbtnp, 1);
  985.             if (bt_nddelkey(btp, rbtnp, 1) == -1) {
  986.                 BTEPRINT;
  987.                 return -1;
  988.             }
  989.         }
  990.     } else {
  991.         memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, rbtnp, 1), btp->bthdr.keysize);
  992.     }
  993. /*printf("NODES AFTER EXTRACT PARENT KEY:\n");
  994. puts("Left:");
  995. bt_dgnode(btp, lbtnp, stdout);
  996. puts("Right:");
  997. bt_dgnode(btp, rbtnp, stdout);*/
  998.  
  999.     /* write lbtnp, rbtnp, and pbtnp to file */
  1000.     if (bt_ndput(btp, *bt_kychildp(pbtnp, pkn - 1), lbtnp) == -1) {
  1001.         BTEPRINT;
  1002.         return -1;
  1003.     }
  1004.     if (bt_ndput(btp, *bt_kychildp(pbtnp, pkn), rbtnp) == -1) {
  1005.         BTEPRINT;
  1006.         return -1;
  1007.     }
  1008.     if (bt_ndput(btp, pnode, pbtnp) == -1) {
  1009.         BTEPRINT;
  1010.         return -1;
  1011.     }
  1012.  
  1013.     errno = 0;
  1014.     return 0;
  1015. }
  1016.  
  1017. /*man---------------------------------------------------------------------------
  1018. NAME
  1019.      bt_ndsplit - btree node split
  1020.  
  1021. SYNOPSIS
  1022.      #include "btree_.h"
  1023.  
  1024.      int bt_ndsplit(btp, node, btnp, rbtnp, bttplp)
  1025.      btree_t *btp;
  1026.      bpos_t node;
  1027.      btnode_t *btnp;
  1028.      btnode_t *rbtnp;
  1029.      bttpl_t *bttplp;
  1030.  
  1031. DESCRIPTION
  1032.      The bt_ndsplit function splits a btree node.  btnp points to an
  1033.      in-core copy of the node to be split.  node is the block number
  1034.      of this node in the file.  The splitting will produce a new right
  1035.      sibling for this node.  Both the modified and the new node are
  1036.      written to the file.  If btnp had a right sibling prior to the
  1037.      split, the lsib link field in that node is updated, also.
  1038.  
  1039.      On return, btnp and rbtnp contain copies of the split node and
  1040.      its new right sibling, respectively, and the tuple pointed to by
  1041.      bttplp contains the (key, child address) tuple to be inserted in
  1042.      the parent of the split node; bttplp->child contains the block
  1043.      number of the new right sibling node.
  1044.  
  1045.      bt_ndsplit will fail if one or more of the following is true:
  1046.  
  1047.      [EINVAL]       btp is not a valid btree pointer.
  1048.      [EINVAL]       btnp, rbtnp, or bttplp is NULL.
  1049.      [BTENOPEN]     btp is not open.
  1050.      [BTEPANIC]     The number of keys in btnp is not equal to m.
  1051.  
  1052. SEE ALSO
  1053.      bt_ndfuse, bt_ndshift.
  1054.  
  1055. DIAGNOSTICS
  1056.      Upon successful completion, a value of 0 is returned.  Otherwise,
  1057.      a value of -1 is returned, and errno set to indicate the error.
  1058.  
  1059. ------------------------------------------------------------------------------*/
  1060. int bt_ndsplit(btp, node, btnp, rbtnp, bttplp)
  1061. btree_t *btp;
  1062. bpos_t node;
  1063. btnode_t *btnp;
  1064. btnode_t *rbtnp;
  1065. bttpl_t *bttplp;
  1066. {
  1067.     bool    leaf    = FALSE;    /* leaf node flag */
  1068.     int    midkn    = 0;        /* middle key number */
  1069.     bpos_t    rnode    = 0;        /* right node block number */
  1070.     int    terrno    = 0;        /* tmp errno */
  1071. #ifdef DEBUG
  1072.     /* validate arguments */
  1073.     if (!bt_valid(btp)) {
  1074.         BTEPRINT;
  1075.         errno = EINVAL;
  1076.         return NULL;
  1077.     }
  1078.     if (btnp == NULL || rbtnp == NULL || bttplp == NULL) {
  1079.         BTEPRINT;
  1080.         errno = EINVAL;
  1081.         return -1;
  1082.     }
  1083.  
  1084.     /* check if not open */
  1085.     if (!(btp->flags & BTOPEN)) {
  1086.         BTEPRINT;
  1087.         errno = BTENOPEN;
  1088.         return NULL;
  1089.     }
  1090.  
  1091.     /* check if node not one over full */
  1092.     if (btnp->n != bt_ndmax(btp) + 1) {
  1093.         BTEPRINT;
  1094.         errno = BTEPANIC;
  1095.         return -1;
  1096.     }
  1097. #endif
  1098.     /* initialize */
  1099.     bt_ndinit(btp, rbtnp);
  1100.  
  1101.     /* check if leaf node */
  1102.     if (bt_ndleaf(btnp)) {
  1103.         leaf = TRUE;
  1104.     }
  1105.  
  1106.     /* get new block for right sibling node */
  1107.     if (bflpop(btp->bp, &rnode) == -1) {
  1108.         BTEPRINT;
  1109.         return -1;
  1110.     }
  1111.  
  1112.     /* fix sibling links */        /*L=left R=right O=old right */
  1113.     rbtnp->rsib = btnp->rsib;    /* L    R -> O */
  1114.     btnp->rsib = rnode;        /* L -> R    O */
  1115.     rbtnp->lsib = node;        /* L <- R    O */
  1116.     if (rbtnp->rsib == NIL) {    /* L    R <- O */
  1117.         if (leaf) btp->bthdr.last = rnode;
  1118.     } else {
  1119.         if (bputbf(btp->bp, rbtnp->rsib, offsetof(btnode_t, lsib),
  1120.                     &rnode, sizeof(rbtnp->lsib)) == -1) {
  1121.             BTEPRINT;
  1122.             terrno = errno;
  1123.             bflpush(btp->bp, &rnode);
  1124.             errno = terrno;
  1125.             return -1;
  1126.         }
  1127.     }
  1128.  
  1129.     /* calculate middle key number */
  1130.     midkn = btnp->n / 2 + 1;
  1131.  
  1132.     /* get middle (key, child) tuple into bttplp */
  1133.     if (bt_kyread(btp, btnp, midkn, bttplp) == -1) {
  1134.         BTEPRINT;
  1135.         terrno = errno;
  1136.         bflpush(btp->bp, &rnode);
  1137.         errno = terrno;
  1138.         return -1;
  1139.     }
  1140.     bttplp->child = rnode;
  1141.  
  1142.     /* shift keys from left sibling */
  1143.     if (leaf) {
  1144.         /* move midkn thru n to right sibling */
  1145.         if (bt_kymvright(btp, btnp, rbtnp, btnp->n - midkn + 1) == -1) {
  1146.             BTEPRINT;
  1147.             return -1;
  1148.         }
  1149.     } else {
  1150.         /* move midkn + 1 thru n to right sibling */
  1151.         if (bt_kymvright(btp, btnp, rbtnp, btnp->n - midkn) == -1) {
  1152.             BTEPRINT;
  1153.             return -1;
  1154.         }
  1155.         /* delete midkn */
  1156.         if (bt_nddelkey(btp, btnp, midkn) == -1) {
  1157.             BTEPRINT;
  1158.             return -1;
  1159.         }
  1160.     }
  1161.  
  1162.     /* write split nodes */
  1163.     if (bt_ndput(btp, node, btnp) == -1) {
  1164.         BTEPRINT;
  1165.         return -1;
  1166.     }
  1167.     if (bt_ndput(btp, rnode, rbtnp) == -1) {
  1168.         BTEPRINT;
  1169.         return -1;
  1170.     }
  1171.  
  1172.     errno = 0;
  1173.     return 0;
  1174. }
  1175.